package 二分查找;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 在排序数组中查找元素首尾位置.java
 * @Description TODO
 * @createTime 2020年11月05日 22:28:00
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 你的算法时间复杂度必须是 O(log n) 级别。
 *
 * 如果数组中不存在目标值，返回 [-1, -1]。
 *
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 * 示例 2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 *
 * 思路：就是左边界和右边界问题
 */
public class 在排序数组中查找元素首尾位置 {
    public class Solution {
        public int[] searchRange(int[] nums, int target) {
            if(nums.length==0){
                return new int[]{-1, -1};
            }

            int left = findleft(nums, target);
            if (left == -1) {
                return new int[]{-1, -1};
            }

            int right = findright(nums, target);
            return new int[]{left, right};
        }

        private int findleft(int[] nums, int target) {
            int left=0;
            int right=nums.length-1;
            while(left<=right){
                int mid=left+(right-left)/2;
                if(nums[mid]>=target){
                    right=mid-1;
                }else if(nums[mid]<target){
                    left=mid+1;
                }
            }

            if(left>=nums.length||nums[left]!=target){
                return -1;
            }
            return left;

        }

        private int findright(int[] nums, int target) {
            int left=0;
            int right=nums.length-1;
            while(left<=right){
                int mid=left+(right-left)/2;
                if(nums[mid]<=target){
                    left=mid+1;
                } else{
                    right=mid-1;
                }

            }

            if(right<0||nums[right]!=target){
                return -1;
            }
            return right;
        }
    }
}
